package com.example.lcpractice.lc;

import com.example.lcpractice.datastructure.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 96. 不同的二叉搜索树
 * 中等
 * 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
 * <p>
 * <p>
 * <p>
 * 输入: 3
 * 输出: 5
 * 解释:
 * 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
 * <p>
 * 1         3     3      2      1
 * \       /     /      / \      \
 * 3     2     1      1   3      2
 * /     /       \                 \
 * 2     1         2                 3
 */
public class Lc96 {
    public static void main(String[] args) {
//        System.out.println(permute(new int[]{3,4,5}));
    }

    /**
     * 思路（动态规划）：
     * 注意：长度相同时的连续数能构成的二叉搜索树的方案数是相同的
     * 如 1 2 3 4 5 和 6 7 8 9 10 能够构成的方案数是相同的（1 2 3 4 5通过值映射就可以得到6 7 8 9 10）。
     *
     * @param n
     * @return
     */
    public static int numTrees(int n) {
        // f[n] 代表对于n个数字有 f[n]种树
        int[] f = new int[n + 1];
        f[0] = 1;
        // 这里如果是加法计数原理的话通常是初始状态为0，乘法计数原理的话初始状态一般是1
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                f[i] += f[j - 1] * f[i - j];
            }
        }
        return f[n];
    }

    /**
     * 递归
     * 注意：长度相同时的连续数能构成的二叉搜索树的方案数是相同的(二叉搜索树只跟数字间相对大小有关)
     * 故n个数字转化成 [1,2```,n-1,n]
     *
     * @param n
     * @return
     */
    public static int numTrees2(int n) {
        int sum = 0;
        if (n <= 1) {
            return 1;
        }

        // 以当前的数为根节点，左右两边的数分别构建子树
        for (int i = 1; i <= n; i++) {
            // 左边的数可以构建多少个二叉搜索树
            // 计算i左边的数字能构成多少种数目
            //比如 【1，2，3，4】 i=1 求 【1，2】
            // 相当去求 去n后能构建多少个数字
            int left_num = numTrees(i - 1);
            // 而二叉树右边仍然保持有序，思考减去i后的种类
            int right_num = numTrees(n - i);
            // 右边的数可以构建多少个二叉搜索树


            //
            sum = sum + left_num * right_num;
        }

        return sum;
    }
}
